#include "Cache.h"
#include <iostream>
#include <cmath>
#include <string>
#include <fstream>
#include <set>

//for perfromance reasons we need to know how much room to allocate for thread statistics
// so we must set a max # of threads to be tracked.  if the number of threads exceeds this, 
//


Cache::Cache(CacheInfo info)
{
    output = false; //have not output results yet
    this->info=info;
    //cout << "cache #" <<this->info.selfID <<" addr: "<<this<<endl;
    
    
    /* create Replacement Policy object 
     
     if you have added a new replacement policy (subclassed ReplacementPolicy)
     then just add an else if here so that the object can be created based on the string
     read from the config file.
     
     */
    
    if(info.policy == "RoundRobin")
        policy = new RoundRobin((info.size/info.blockSize)/info.assoc, info.assoc);
    else if(info.policy == "LRU")
        policy = new LRU((info.size/info.blockSize)/info.assoc, info.assoc);
    else{
        cout<<"program will exit. You have entered an invalid replacement policy: "<<info.policy;
        exit(840);
    }
    
    initCache();
    
    
    tagMask = ~UINT64(UINT64(info.size/info.assoc)-1);
    
    //indexMask is used to mask away the tag and the position in the set.
    indexMask = UINT64(info.size/info.blockSize)-UINT64(info.assoc);
    
    //the assoc paramter below would not normally be in an index shift, 
    //but because the array is 1d instead of 2d (rows are blocks and not sets)
    // we shift less shift according to associativity
    // really we are pointing to a block, not a set, so instead of set# its set#* assoc
    
    indexShift = log2(info.blockSize/info.assoc);
    
    //block mask is used to find the first byte in the block
    blockMask = ~UINT64(info.blockSize-1);
    
   //   cout <<"tag mask" <<hex<<tagMask;
 //   cout<<"\nindex mask = "<<hex<<indexMask;
 //   cout<<"\n index shift = "<<dec << indexShift<<endl<<endl;
   //   cout <<"block mask = "<<hex<<blockMask<<endl;
    blockSizeShift = log2(info.blockSize);
    
    
}

void Cache::initCache(){
    
    info.numRows = (info.size/info.blockSize)/info.assoc;
    
    cache = new UINT64[info.numRows*(info.assoc)];
    status = new UINT8[info.numRows*(info.assoc)];
    
    if (cache == NULL || status == NULL){
        cout<< "could not allocate " 
        << (sizeof(UINT64)+sizeof(UINT8))*info.numRows*info.assoc
        <<" bytes of memory for a cache. Exiting.";
        exit(5);
    }
    for(UINT64 i=0; i<info.numRows*(info.assoc);i++){
        cache[i]=0;
        status[i]=0;
        
    }
    //init statistics array
    for(int i=0;i<MAXTHREADS;i++)
        for(int j=0;j<256;j++)
            stats[i][j]=0;
    
    
    
}

CacheInfo Cache::getCacheInfo(){
    
    return info;
}

void Cache::searchCache(UINT64 addr, int threadid, bool write, ofstream& debug, UINT64 icount){
    
    
    //mask block offset and index for tag
    UINT64 tag = UINT64(addr) & tagMask;
    
    //mask tag and then shift away the block offset for the starting block of the index
    // note that this is not the index number, but the first block number in the desired index
    // or simply index number *associativity.
    
    UINT64 block = ((addr >> indexShift) & indexMask);
    
    
    for (unsigned int i=0;i<info.assoc;i++){
       if( cache[block+i] == tag ) { //if matching tag 
            if(!write){ //if read request
                stats[threadid][status[block+i]]++; //record stats for read
                if(!(status[block+i] & 1)){ //if invalid
                    UINT8 states = 0;
                    for(int j = 0; j < numSiblings; j++){
                        //check each sibling and keep track of who has block. dont invalidate
                        states = states & (siblings[j]-> checkCache(addr&blockMask, info.blockSize,0,1,debug, icount));
                    }
                    if (!(states & 1)) //if no sibling had it (or no siblings)
                        if(parent!=NULL)
                            parent->searchCache(addr & blockMask, threadid,0,debug, icount);
                    status[block+i] = status[block+i] | 1; //mark as valid(shared)
                    if(icount <info.debugLimit)
                        debug<<dec<<icount<<":"<<hex<<addr<<". read miss in c:"<<dec<<info.selfID<<". block invalid"<<hex<<tag<<endl;
                    if(icount<info.debugLimit)
                        cacheDump(debug);
                }
                else{
                    policy->blockUsed(block, i);
                    if(icount < info.debugLimit)
                        debug<<dec<<icount<<":"<<hex<<addr<<". read hit in c:"<<dec<<info.selfID<<endl;
                }
            }
            else{ //write request
                stats[threadid][status[block+i]+128]++; //record stats for write
                if(status[block+i]&1){ //if valid ( at least shared)
                    policy->blockUsed(block, i);
                    if(icount < info.debugLimit)
                        debug<<dec<<icount<<":"<<hex<<addr<<". write hit in c:"<<dec<<info.selfID<<endl;
                    if ((status[block+i]&2)){//if owner(modified)
                        return;
                    }   
                    else{ //not owner (but shared)
                        for(int i = 0; i<numSiblings;i++)
                            //invalidate siblings. don't need data.
                            siblings[i]-> checkCache(addr&blockMask, info.blockSize,1,0,debug,icount); 
                        if(parent!=NULL)
                            parent->getOwnership(addr&blockMask,debug,icount);
                    }
                }
                else{ //if not valid
                    if(icount <info.debugLimit)
                        debug<<dec<<icount<<":"<<hex<<addr<<". write miss in c:"<<dec<<info.selfID<<". block invalid "<<hex<<tag<<endl;
                    UINT8 states = 0;
                    for(int i = 0; i < numSiblings; i++)
                        // read states and invalidate
                        states = states & siblings[i]-> checkCache(addr &blockMask, info.blockSize,1,0,debug, icount); 
                    if(states & 1){//if a sibling had data
                        if(parent!=NULL)
                            parent->getOwnership(addr&blockMask,debug,icount);//only need parent to get ownership
                    }   
                    else{ //if no siblings had  data
                        if(parent!=NULL)
                            parent->searchCache(addr & blockMask, threadid, 1,debug, icount);
                    }
                }
                status[block+i] = status[block+i] | 3; //mark valid & owner (modified)
                if(icount<info.debugLimit)
                    cacheDump(debug);
            }
            return;    
        } //end if matching tag
    }
    //block not in cache
    
    if(!write){ //read request 
        if(icount < info.debugLimit)
            debug<<dec<<icount<<":"<<hex<<addr<<". read miss in c:"<<dec<<info.selfID<<". tag: "<<hex<<tag<<" block "<<block<<" set: "<<block/info.assoc<<endl;
        stats[threadid][127]++; // tag not found read miss 
        UINT8 states = 0;
        for(int i = 0; i < numSiblings; i++){
            //check each sibling and keep track of who has block. dont invalidate
            states = states & (siblings[i]-> checkCache(addr&blockMask, info.blockSize,0,1,debug,icount));
        }
        if (!(states & 1)) //if no sibling had it (or no siblings)
            if(parent!=NULL)
                parent->searchCache(addr & blockMask, threadid,0,debug, icount);
    }
    else{
        if(icount <info.debugLimit)
            debug<<dec<<icount<<":"<<hex<<addr<<"write miss in c:"<<dec<<info.selfID<<". tag: "<<hex<<tag<<" block "<<block<<" set: "<<block/info.assoc<<endl;
        stats[threadid] [255]++; //tag not found write miss
        UINT8 states = 0;
        for(int i = 0; i < numSiblings; i++){
            // read states and invalidate
            states = states & (siblings[i]-> checkCache(addr&blockMask, info.blockSize,1,0,debug,icount)); 
        }
        if(states & 1){//if a sibling had data
            if(parent!=NULL)
                parent->getOwnership(addr&blockMask,debug,icount);//only need parent to get ownership
        }
        else{ //if no siblings had  data
            if(parent!=NULL)
                parent->searchCache(addr & blockMask, threadid, 1,debug,icount);
        }
    }
    
    //the only thing left to do is to find a place for the new block.
    
    int evicteePos; //set offset of the evictee
    UINT64 evictee; //address of evictee
    for(unsigned int i=0; i<info.assoc;i++)
        if(!(status[block+i]&1)){ //look for an invalid block in the set
            evicteePos = i; // found it...
            cache[block+evicteePos] = tag; //store tag in cache
            if(!write)
                status[block+i] = status[block+i] | 1; //mark as valid(shared)
            else
                status[block+i] = status[block+i] | 3; //mark valid & owner (modified)
            if(icount < info.debugLimit){
                debug<<dec<<icount<<":"<<hex<<cache[block+evicteePos]<<". stored in  c:"<<dec<<info.selfID<<". tag: "<<hex<<tag<<" set: "<<block/info.assoc<<" pos: "<<i<<endl;
                cacheDump(debug);
            }
            return; // we put the new block in an invalid blocks place and updated status
        }
    
    evicteePos = policy->chooseEvictee(block); //choose evictee via replacement policy
    evictee = cache[block+evicteePos]; //save it to invalidate children
    cache[block+evicteePos] = tag; //store the tag in cache   
    stats[threadid][48]++;//record eviction      
    
    for(int i=0; i<numChildren; i++)
        children[i]->invalidate(evictee,info.blockSize,debug,icount);//invalidate evicted block from children (fully inclusive)
    if(icount <info.debugLimit){
        debug<<dec<<icount<<": block #"<<evicteePos<<" chosen for eviction in cache:"<<dec<<info.selfID<<endl;
        debug<<dec<<icount<<":"<<hex<<cache[block+evicteePos]<<" stored in c:"<<dec<<info.selfID<<". tag: "<<hex<<tag<<" set: "<<block/info.assoc<<endl;
        cacheDump(debug);
    }
    if(!write)
        status[block+evicteePos] = status[block+evicteePos] | 1; //mark as valid(shared)
    else
        status[block+evicteePos] = status[block+evicteePos] | 3; //mark valid & owner (modified)
    
}

void Cache::getOwnership(UINT64 addr,ofstream& debug, UINT64 icount){
    

    UINT64 tag = addr & tagMask;
    UINT64 block = ((addr >> indexShift) & indexMask);
    
    if(icount<info.debugLimit){
        debug<<dec<<icount<<":I have to get ownership. c:"
        <<info.selfID<<hex<<" set:"<<block/info.assoc<<" addr:"<<addr<<endl;
    }
   
        
    for (unsigned int i=0;i<info.assoc;i++){
        if( cache[block+i] == tag ){
            status[block+i]=status[block+i] | 3;
            if(icount<info.debugLimit)
                cacheDump(debug);
            for(int i = 0; i<numSiblings;i++)
                //invalidate siblings. don't need data.
                siblings[i]-> checkCache(addr&blockMask, info.blockSize,1,0,debug,icount); 
            if(parent!=NULL)
                parent->getOwnership(addr&blockMask,debug,icount);
            return;
        }
    }
    if(icount<info.debugLimit)
        debug<<endl<<"ERROR.. i should have this block but i don't! c:"
        <<info.selfID<<hex<<" block:"<<block<<"addr: "<<addr<<endl;
    
    
    
    
}

void Cache::invalidate(UINT64 start, int numBytes, ofstream& debug,UINT64 icount){
    
    
    if(icount <info.debugLimit)
        debug<<dec<<icount<<":block #"<<hex<<start<<" invalidation request in cache:"<<dec<<info.selfID<<endl;
        
    int loops = numBytes >> blockSizeShift; //calculate how many times bigger the calling blockSize is than local blockSize
    if (loops == 0) //this cache has larger blocks than calling cache, so...
        loops=1; //just one loop
    
    for (int i=0; i<loops; i++){
        UINT64 tag = start & tagMask;
        UINT64 block = ((start >> indexShift) & indexMask);
        for (unsigned int i=0;i<info.assoc;i++){
            if( cache[block+i] == tag ){
                if(icount <info.debugLimit){
                    debug<<dec<<icount<<": "<<hex<<start<<" found in ."<<dec<<info.selfID<<".  invalidated."<<endl;
                    cacheDump(debug);
                }
                status[block+i]=status[block+i] & (~3);
                for(int i=0; i<numChildren;i++)
                    children[i]->invalidate(start,info.blockSize, debug, icount);
                return;
            }
        }
        start = start+info.blockSize; 
    }
}

void Cache::goShared(UINT64 start, int numBytes, ofstream& debug,UINT64 icount){
    
    
    
    int loops = numBytes >> blockSizeShift; //calculate how many times bigger the calling blockSize is than local blockSize
    if (loops == 0) //this cache has larger blocks than calling cache, so...
        loops=1; //just one loop
    
    for (int i=0; i<loops; i++){
        UINT64 tag = start & tagMask;
        UINT64 block = ((start >> indexShift) & indexMask);
        for (unsigned int i=0;i<info.assoc;i++){
            if( cache[block+i] == tag ){
                status[block+i]=status[block+i] & (~2);//removed modified state
                for(int i=0; i<numChildren;i++) ///make children removed modified state
                    children[i]->goShared(start,info.blockSize, debug, icount);
                return;
            }
        }
        start = start+info.blockSize; 
    }
}

UINT8 Cache::checkCache(UINT64 start, int numBytes, bool inv, bool check, ofstream &debug,UINT64 icount){
    
    
    int loops = numBytes >> blockSizeShift; //calculate how many times bigger the calling blockSize is than local blockSize
    if (loops == 0) //this cache has larger blocks than calling cache, so...
        loops=1; //just one loop
    
    UINT8 states=0;
    //if need to return wether we found state, start at 1 and set to 0 only if a block wasn't found.
    
    if(check)
        states=1;
    
    for (int i=0; i<loops; i++){
        
        if(check){
            UINT8 inLoop = 0;
            //mask block offset and index for tag
            UINT64 tag = start & tagMask;
            
            //shift away block offset and then mask away tag for the starting block of the index
            // note that this is not the index number, but the first block number in the desired index
            // or simply index number *associativity.
            
            UINT64 block = ((start >> indexShift) & indexMask);
            for (unsigned int i=0;i<info.assoc;i++){
                if( cache[block+i] == tag ){  //if matching tag 
                    inLoop = inLoop | status[block+i]; //seeing if any block matches and is valid
                    status[block+i]=status[block+i]&(~2);//move state from M to S(or still I if I)
                    for(int i=0; i<numChildren;i++)//have to make sure no children keep in modified
                        children[i]->goShared(start,info.blockSize, debug, icount);
                    break;
                }
            }
            
            if(!(inLoop&1))
                states = 0;
        }
        
        if(inv)
            invalidate(start,info.blockSize,debug,icount);
        start = start+info.blockSize;               
    }
    if(states&1)
        if(icount <info.debugLimit)
            debug<<dec<<icount<<hex<<": block #: "<<start<<". shared from c:"<<dec<<info.selfID<<endl;
    return states;
}




void Cache::printStats(ofstream &out,set<int> processed){
    
    if(output)
        return;
    output=true;
    
    //print any remaining children before printing self
    for(int i=0; i<numChildren; i++)
        children[i]->printStats(out,processed);
    out <<"\n======================================";
    out << "\nstats for cache: " << info.selfID <<" ("<<info.desc<<")"<< endl << endl;
    
    
    for (int i=0; i<MAXTHREADS; i++){
        if(stats[i][127]+stats[i][255]){//if there are any read or write misses for the thread
            if(i>0)
                out <<"\n- - - - - - - - - - - - - - - - - - -";
            out << "\n\nthread #: "<<i<<endl;
            out << "\nread hits in M state:" <<stats[i][3];
            out << "\nread hits in S state:" <<stats[i][1];
            out <<"\nwrite hits in M state:"<<stats[i][3+128];
            out <<"\nwrite hits in S state:"<<stats[i][1+128];
            UINT64 hits = stats[i][3]+stats[i][1]+stats[i][131]+stats[i][129];
            out <<"\ntotal hits:"<<hits;
            out <<"\n\ntotal evictions: "<<stats[i][48];
            out <<"\n\nreads misses, block in cache but invalid:"<<stats[i][0]+stats[i][2];
            out <<"\nwrite misses, block in cache but invalid:"<<stats[i][128]+stats[i][130];
            out <<"\nread misses, not in cache:"<<stats[i][127];
            out <<"\nwrite misses, not in cache:"<<stats[i][255];
            UINT64 misses = stats[i][0]+stats[i][2]+stats[i][128]+stats[i][130]+stats[i][127]+stats[i][255];
            out<<"\n\ntotal misses:"<< misses;
            out<<"\nmisses per 1000 accesses:" << (float(misses)/float(hits+misses))*1000;
            out<<"\n\ntotal reads:"<<stats[i][3]+stats[i][1]+stats[i][0]+stats[i][2]+stats[i][127];
            out<<"\n total writes:"<<stats[i][131]+stats[i][129]+stats[i][128]+stats[i][130]+stats[i][255]<<endl<<endl;
        }
    }
    processed.insert(info.selfID);
    //print siblings
    for(int i=0; i<numSiblings; i++)
        siblings[i]->printStats(out,processed);
    //print parent if exists
    if(parent!=NULL)
        parent->printStats(out, processed);
    return;
    
}




void Cache::cacheDump(ofstream& out){
    
    if(!info.dump)
        return;
    
    out<<hex<<endl<<"cache: "<<info.selfID;
    for(unsigned int i=0; i<info.numRows; i++){
        out<<endl<<i<<": ";
        for (unsigned int j=0; j<info.assoc; j++)
            out<<cache[i*info.assoc+j]<<", ";
        
    }
    
        out<<endl<<"status of cache: "<<info.selfID;
        for(unsigned int i=0; i<info.numRows; i++){
            out<<endl<<i<<": ";
            for (unsigned int j=0; j<info.assoc; j++)
                out<<(status[i*info.assoc+j]&3)<<", ";
            
            

    }
    out<<endl<<endl;
    
}


void Cache::setParent(Cache* parent){
    this->parent = parent;
    //cout << "cache #" <<this->info.selfID <<" parent: "<<this<<endl;

    
    
}
void Cache::setChildren(Cache** children, int numChildren){
    
    this->children = new Cache*[numChildren];
    this->numChildren = numChildren;
    for (int i=0; i<numChildren; i++)
        this->children[i] = children[i];
    
}
void Cache::setSiblings(Cache** siblings, int numSiblings){
    
    this->siblings = new Cache* [numSiblings];
    this->numSiblings = numSiblings;
    for (int i=0; i<numSiblings; i++)
        this->siblings[i] = siblings[i];
}

Cache * Cache::getParent(){
    return parent;
    
}
